#define _CRT_SECURE_NO_WARNINGS 1
class Solution {

    int k_mi(int a, int b, int p) {
        int res = 1;
        while (b) {
            if (b & 1)res = res * a % p;
            b >>= 1;
            a = a * a % p;
        }
        return res;
    }
public:
    vector<int> getGoodIndices(vector<vector<int>>& variables, int target) {
        int len = variables.size();
        vector<int> ans;
        for (int i = 0; i < len; i++) {
            int k = k_mi(variables[i][0], variables[i][1], 10);
            if (k_mi(k, variables[i][2], variables[i][3]) == target) {
                ans.push_back(i);
            }
        }
        return ans;
    }
};